#include <iostream>
#include <fstream>
#include <vector>
#include <algorithm>

using namespace std;

// 点结构体
struct Point {
    int x, y;
};

// 比较函数，用于排序
bool compare(Point a, Point b) {
    return a.x < b.x || (a.x == b.x && a.y < b.y);
}

// 计算两点之间的叉积
int crossProduct(Point O, Point A, Point B) {
    return (A.x - O.x) * (B.y - O.y) - (A.y - O.y) * (B.x - O.x);
}

vector<Point> dividedConvexHull(vector<Point>& points) {
    int n = points.size();

    // 按照 x 坐标排序
    sort(points.begin(), points.end(), compare);

    // 构建下凸包
    vector<Point> lowerHull;
    for (int i = 0; i < n; ++i) {
        while (lowerHull.size() >= 2 && crossProduct(lowerHull[lowerHull.size() - 2], lowerHull.back(), points[i]) <= 0) {
            lowerHull.pop_back();
        }
        lowerHull.push_back(points[i]);
    }

    // 构建上凸包
    vector<Point> upperHull;
    for (int i = n - 1; i >= 0; --i) {
        while (upperHull.size() >= 2 && crossProduct(upperHull[upperHull.size() - 2], upperHull.back(), points[i]) <= 0) {
            upperHull.pop_back();
        }
        upperHull.push_back(points[i]);
    }

    // 合并凸包
    lowerHull.pop_back();  // 删除重复的点
    upperHull.pop_back();
    lowerHull.insert(lowerHull.end(), upperHull.begin(), upperHull.end());

    return lowerHull;
}

//int main() {
//    // 打开文件
//    ifstream inputFile("random_points_100.txt");
//    if (!inputFile.is_open()) {
//        cerr << "Error opening file.\n";
//        return 1;
//    }
//
//    // 读取文件中的点坐标
//    vector<Point> points;
//    int x, y;
//    while (inputFile >> x >> y) {
//        points.push_back({x, y});
//    }
//    inputFile.close();
//
//    // 计算凸包
//    vector<Point> result = dividedConvexHull(points);
//
//    // 输出凸包的点坐标
//    cout << "Convex Hull Points:\n";
//    for (const auto& point : result) {
//        cout << "(" << point.x << ", " << point.y << ")\n";
//    }
//
//    return 0;
//}
